package data_structure.tensort;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @className: Sort 提供了各种各样的排序的方法
 */
public class Sort {
    /**
     * 冒泡排序 bubbleSort
     *
     * @param a 原始数组
     * @return 排序后的数组
     */

    public static int[] bubbleSort(int[] a) {
        int temp = 0;
        for (int i = 1; i < a.length; i++) {
            for (int j = 0; j < a.length - i; j++) {
                if (a[j] > a[j + 1]) {
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
        return a;
    }

    /**
     * 选择排序 selectionSort
     *
     * @param a 原始数组
     * @return 排序后的数组
     */
    public static int[] selectionSort(int a[]) {
        int temp;
        int length = a.length;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if (a[j] > a[i]) {
                    temp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = temp;
                }
            }
        }
        return a;
    }

    /**
     * 插入排序 insertionSort
     *
     * @param a 原始数组
     * @return 排序后的数组
     */
    public static int[] insertionSort(int a[]) {
        int length = a.length;
        for (int i = 0; i < length - 1; i++) {
            int preIndex = i;
            int current = a[preIndex + 1];
            while (preIndex >= 0 && a[preIndex] > current) {
                a[preIndex + 1] = a[preIndex];
                preIndex--;
            }
            a[preIndex + 1] = current;
        }
        return a;
    }

    /**
     * 希尔排序 shellSort
     *
     * @param a
     * @return
     */
    public static int[] shellSort(int[] a) {
        int length = a.length;
        int temp, gap = length / 2;// 希尔增量
        while (gap > 0) {
            for (int i = gap; i < length; i++) {
                temp = a[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && a[preIndex] > temp) {
                    a[preIndex + gap] = a[preIndex];
                    preIndex -= gap;
                }
                a[preIndex + gap] = temp;
            }
            gap /= 2;
        }
        return a;
    }

    /**
     * 归并算法 mergeSort
     *
     * @param a 原始数组
     * @return 排序后数组
     */
    public static int[] mergeSort(int a[]) {
        if (a.length < 2)
            return a;
        int mid = a.length / 2;
        int left[] = Arrays.copyOfRange(a, 0, mid);
        int right[] = Arrays.copyOfRange(a, mid, a.length);
        return merge(mergeSort(left), mergeSort(right));
    }

    /**
     * 归并函数 merge 用来将两个排好序的数组合并成一个新的有序数组
     *
     * @param left
     * @param right
     * @return
     */
    public static int[] merge(int left[], int right[]) {
        int result[] = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= left.length) {
                result[index] = right[j++];
            } else if (j >= right.length) {
                result[index] = left[i++];
            } else if (left[i] > right[j]) {
                result[index] = right[j++];
            } else
                result[index] = left[i++];
        }
        return result;
    }

    /**
     * 快速排序 quickSort 方法要点：基准 分区 递归
     *
     * @param a     数组
     * @param left  排序开始位置
     * @param right 排序完成位置
     * @return
     */
    public static int[] quickSort(int a[], int left, int right) {
        if (right >= a.length || left < 0 || left > right) {
            return null;
        }
        int smallIndex = partition(a, left, right);
        if (left < smallIndex)
            quickSort(a, left, smallIndex - 1);
        if (right > smallIndex)
            quickSort(a, smallIndex + 1, right);
        return a;
    }

    /**
     * 快速排序-分区函数 partition
     *
     * @param a
     * @param start
     * @param end
     * @return
     */
    public static int partition(int a[], int start, int end) {
        int pivot = (int) (start + Math.random() * (end - start + 1));
        int smallIndex = start - 1;
        swap(a, pivot, end);
        for (int i = start; i <= end; i++)
            if (a[i] <= a[end]) {
                smallIndex++;
                if (i > smallIndex) {
                    swap(a, i, smallIndex);
                }
            }
        return smallIndex;
    }

    /**
     * 快速排序-交换函数 swap
     *
     * @param a 数组
     * @param i 交换位置
     * @param j 交换位置
     */
    public static void swap(int a[], int i, int j) {
        int temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    /**
     * 堆排序 heapSort 注意定义静态变量 len---数组的长度
     *
     * @param a
     * @return
     */
    static int len;

    public static int[] heapSort(int a[]) {
        len = a.length;
        // 构建最大堆
        buildMaxHeap(a);
        // 交换顶点和最后一个非叶子节点的值，并且调整新堆为最大堆
        while (len > 0) {
            swap(a, 0, len - 1);
            len--;
            adjustHeap(a, 0);
        }
        return a;
    }

    /**
     * 构建最大堆 buildMaxHeap 从最后一个非叶子节点向上开始构建开始构建
     *
     * @param a
     */
    public static void buildMaxHeap(int a[]) {

        for (int i = (len / 2 - 1); i >= 0; i--) {
            adjustHeap(a, i);
        }
    }

    /**
     * 调整堆为最大堆 adjustHeap
     *
     * @param a
     * @param i
     */
    public static void adjustHeap(int a[], int i) {
        int maxIndex = i;

        if (i * 2 < len && a[i * 2] > a[maxIndex]) {
            maxIndex = i * 2;
        }
        if (i * 2 + 1 < len && a[i * 2 + 1] > a[maxIndex]) {
            maxIndex = i * 2 + 1;
        }
        if (maxIndex != i) {
            swap(a, i, maxIndex);
            adjustHeap(a, maxIndex);
        }
    }

    /**
     * 计数排序 countSort 依据键值的重复的个数来装桶
     *
     * @param a
     * @return
     */
    public static int[] countSort(int a[]) {
        int length = a.length;
        if (a.length == 0)
            return null;
        int bias;// 基准值
        int min = a[0], max = a[0];
        for (int i = 0; i < length; i++) {
            if (a[i] >= max) {
                max = a[i];
            }
            if (a[i] <= min) {
                min = a[i];
            }
        }
        bias = 0 - min;// 基准值
        int bucket[] = new int[max - min + 1];// 用来计入数组a中各数据出现的次数
        for (int i = 0; i < length; i++) {
            bucket[a[i] + bias]++;
        }
        // 遍历bucket数组
        int index = 0, i = 0;
        while (index < length) {
            if (bucket[i] != 0) {
                a[index] = i - bias;
                index++;
                bucket[i]--;
            } else {
                i++;
            }
        }
        return a;
    }

    /**
     * 桶排序 bucketSort 依据键值的大致范围来装桶 分桶和装桶 遍历桶---注意随着bucketSize要逐步的减少
     *
     * @param array      ArrayList<Integer>
     * @param bucketSize int 桶内数据的范围
     * @return ArrayList<Integer>
     */
    public static ArrayList<Integer> bucketSort(ArrayList<Integer> array, int bucketSize) {
        if (array.size() == 0 || array.size() < 2) {
            return array;
        }
        ArrayList<Integer> result = new ArrayList<Integer>();
        int max = array.get(0);
        int min = array.get(0);
        for (int i = 0; i < array.size(); i++) {
            if (array.get(i) > max) {
                max = array.get(i);
            }
            if (array.get(i) < min) {
                min = array.get(i);
            }
        }
        int bucketCount = (max - min) / bucketSize + 1;// 确定桶的数量
        ArrayList<ArrayList<Integer>> bucket = new ArrayList<>(bucketCount);// 创建桶
        // 桶的初始化
        for (int i = 0; i < bucketCount; i++) {
            bucket.add(new ArrayList<Integer>());
        }
        // 装桶
        for (int i = 0; i < array.size(); i++) {
            bucket.get((array.get(i) - min) / bucketSize).add(array.get(i));
        }
        // 遍历桶内的元素，先遍历桶，再遍历桶内的数据
        for (int i = 0; i < bucketCount; i++) {
            // 遍历重复的元素
            if (bucketSize == 1) {
                for (int j = 0; j < bucket.get(i).size(); j++) {
                    result.add(bucket.get(i).get(j));
                }

            } else {
                // 当痛的数量为1时，要不断地减小桶的大小
                if (bucketCount == 1) {
                    bucketSize--;
                }
                // 对当前的桶运用桶排序
                ArrayList<Integer> temp = bucketSort(bucket.get(i), bucketSize);
                for (int j = 0; j < temp.size(); j++) {
                    result.add(temp.get(j));
                }

            }
        }
        return result;
    }

    /**
     * 基数排序 radixSort 依据键值的位数来装桶
     *
     * @param array
     * @return
     */
    public static int[] radixSort(int array[]) {
        if (array == null || array.length < 2) {
            return array;
        }
        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        int maxDix = 0;
        while (max != 0) {
            max /= 10;
            maxDix++;
        }
        ArrayList<ArrayList<Integer>> bucket = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            bucket.add(new ArrayList<Integer>());
        }
        int mod = 10, div = 1;
        // 完成装桶和遍历桶内元素操作
        for (int i = 0; i < maxDix; i++, mod *= 10, div *= 10) {
            for (int j = 0; j < array.length; j++) {
                int num = (array[j] % mod) / div;
                bucket.get(num).add(array[j]);
            }
            // 遍历桶内元素
            int index = 0;
            for (int k = 0; k < bucket.size(); k++) {
                for (int j = 0; j < bucket.get(k).size(); j++) {
                    array[index++] = bucket.get(k).get(j);
                }
                bucket.get(k).clear();// 遍历完成之后清空元素
            }
        }

        return array;
    }


}